#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N=5e5+10;
int n,m,q,u,v,fa[N],a[N],tr[N],lst[N];
struct node{
	int l,r,k,d,res,ans;
}qs[N];
inline int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
inline void upd(int x,int y){
	if(!x) return;
	for(;x<=n;x+=lowbit(x))
		tr[x]+=y;
}
inline int qry(int x){
	int res=0;
	for(;x;x-=lowbit(x))
		res+=tr[x];
	return res;
}
inline bool cmp(node p,node q){
	return p.r<q.r;
}
inline bool cmp1(node p,node q){
	return p.l>q.l;
}
inline bool cmp2(node p,node q){
	return p.d<q.d;
}
inline int get(int x){
	int l=1,r=n,res=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(qry(mid)>=x) r=mid-1,res=mid;
		else l=mid+1;
	}
	return res;
}
struct Tnode{
	int l,tag,mn;
}T[N<<2];
inline void build(int u,int l,int r){
	T[u].l=l;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
inline void maketag(int u,int x){
	T[u].tag=x,T[u].mn=T[u].l-x+1;
}
inline void pushdown(int u){
	if(T[u].tag){
		maketag(u<<1,T[u].tag),maketag(u<<1|1,T[u].tag);
		T[u].tag=0;
	}
}
inline void pushup(int u){
	T[u].mn=min(T[u<<1].mn,T[u<<1|1].mn);
}
inline void update(int u,int l,int r,int L,int R,int x){
	if(l>=L&&r<=R) maketag(u,x);
	else{
		int mid=(l+r)>>1;
		pushdown(u);
		if(L<=mid) update(u<<1,l,mid,L,R,x);
		if(R>mid) update(u<<1|1,mid+1,r,L,R,x);
		pushup(u);
	}
}
inline int query(int u,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[u].mn;
	else{
		int mid=(l+r)>>1,res=n;
		pushdown(u);
		if(L<=mid) res=min(res,query(u<<1,l,mid,L,R));
		if(R>mid) res=min(res,query(u<<1|1,mid+1,r,L,R));
		return res;
	}
}
signed main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		u=find(u),v=find(v);
		if(u!=v) fa[u]=v;
	}
	for(int i=1;i<=n;i++)
		a[i]=find(i);
	for(int i=1;i<=q;i++){
		cin>>qs[i].l>>qs[i].r;
		qs[i].d=i;
	}
	sort(qs+1,qs+q+1,cmp);
	int t=0;
	for(int i=1;i<=n;i++){
		upd(lst[a[i]],-1),upd(i,1),lst[a[i]]=i;
		while(t<q&&qs[t+1].r==i)
			t++,qs[t].k=qry(i)-qry(qs[t].l-1);
	}
	sort(qs+1,qs+q+1,cmp1),memset(tr,0,sizeof(tr));
	t=0;
	for(int i=1;i<=n;i++)
		lst[i]=n+1;
	for(int i=n;i>=1;i--){
		upd(lst[a[i]],-1),upd(i,1),lst[a[i]]=i;
		while(t<q&&qs[t+1].l==i)
			t++,qs[t].res=get(qs[t].k);
	}
	t=0;
	for(int i=1;i<=n;i++)
		lst[i]=n+1;
	build(1,1,n);
	for(int i=n;i>=1;i--){
		update(1,1,n,i,lst[a[i]]-1,i),lst[a[i]]=i;
		while(t<q&&qs[t+1].l==i)
			t++,qs[t].ans=query(1,1,n,qs[t].res,qs[t].r);
	}
	sort(qs+1,qs+q+1,cmp2);
	for(int i=1;i<=q;i++)
		cout<<qs[i].ans<<"\n";
	return 0;
}
